The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Referring now to FIG. 1A, a functional data flow diagram depicts the encoding of a data block according to the advanced encryption standard (AES). AES encrypts a 128-bit block of plaintext into a 128-bit block of ciphertext based upon a key. The key length may be 128 bits, 192 bits, or 256 bits. AES is performed using multiple rounds (Nr). For example, when using a 128-bit AES key, a minimum of ten rounds of encryption are performed (Nr=10).
The first step of AES is key addition 102, where the 128-bit plaintext block is XOR'd with the AES key. The output of key addition 102 is transmitted to a multiple-round encryption module 104. The multiple-round encryption module 104 includes byte substitution 106, row shifting 108, column mixing 110, and key addition 112. The multiple-round encryption module 104 operates Nr−1 times on each AES block.
The output of the multiple-round encryption module 104 is transmitted to a final-round encryption module 114, which is similar to the multiple-round encryption module 104, with the removal of column mixing 110. The output of the final-round encryption module 114 is an encrypted 128-bit block of ciphertext. Decryption is performed similarly, with modifications to byte substitution 106 and column mixing 110.
In further detail, key addition 112 receives a round key from a key expansion module 116. The key expansion module 116 creates a round key for each of the rounds of encryption based upon the received AES key. The key expansion section 116 includes a multiple-round key expansion module 118 and a final-round key expansion module 120. The operation of the final-round key expansion module 120 is similar to that of the multiple-round key expansion module 118.
The multiple-round key expansion module 118 operates Nr−1 times to generate a round key for each of the Nr−1 key additions 112 of the multiple-round encryption module 104. The multiple-round key expansion module 118 includes word substitution 122, round constant determination 124, and logical XOR 126.
Word substitution 122 may replace each 8-bit value of a 32-bit word of the key using similar logic as byte substitution 106, which is discussed in more detail below. Round constant determination 124 may retrieve a round constant from a lookup table. Logical XOR 126 may XOR the transformed word with the round constant from round constant determination 124.
The 128-bit input block for AES encryption and the output of each round of AES encryption may be viewed as a 4×4 grid of 8-bit elements (4×4×8=128 bits) referred to as the AES state. Row shifting 108 cyclically shifts each element over in each row of the AES state. Column mixing 110 uses a column of the AES state as a polynomial, multiplies that polynomial by a predetermined polynomial, and stores the result in the same column of the AES state. Column mixing 110 is performed for each column of the AES state.
Further discussion of AES encryption and decryption can be found in Federal Information Processing Standards Publication 197, “Announcing the Advanced Encryption Standard,” National Institute of Standards and Technology, Nov. 26, 2001, the disclosure of which is incorporated herein by reference in its entirety.
Byte substitution 106 replaces each 8-bit element of the AES state with a corresponding 8-bit element. This replacement may be performed using a simple look-up table. To quickly perform AES encryption, the module that performs byte substitution 106, called the S-box, may be instantiated for each of the 16 elements of the AES state. Substitutes for each of the 16 elements of the AES state can then be determined concurrently by 16 S-boxes.
Implementing 16 copies of a look-up table in hardware requires a large number of logic gates. Alternatively, the S-box can determine replacement elements based on the mathematical description of byte substitution 106. The mathematical description includes performing an inversion of the element in a Galois Field (GF). The inversion, performed in GF(256) for the 8-bit value (28=256), is difficult to implement quickly and size-efficiently in hardware.
One of the inventors of AES, Vincent Rijmen, has disclosed a way of reducing the complexity of a mathematical S-box. The disclosure of “Efficient Implementation of the Rijndael S-box,” available at http://www.iaik.tugraz.at/research/krypto/AES/oldhijmen/rijndael/sbox.pdf, is incorporated herein by reference in its entirety. Rijmen suggests decomposing the 8-bit GF(256) element into two 4-bit GF(16) elements.
Operations in the GF(16) domain, and especially inversion, require less processing overhead, allowing the byte substitution 106 to be performed in a reasonable time. The 4-bit elements can then be converted back to an 8-bit value. One implementation of this decomposition and resulting GF(16) operations is presented in FIG. 1B.
Further discussion of the mathematics behind the S-box can be found in “An ASIC Implementation of the AES SBoxes,” Johannes Wolkerstorfer, Elisabeth Oswald, & Mario Lamberger, Proceedings of the Cryptographer's Track at the RSA Conference 2002, San Jose, Calif., USA, Lecture Notes in Computer Science Vol. 2271/2002, February 2002, the disclosure of which is incorporated herein by reference in its entirety.
Referring now to FIG. 1B, a functional block diagram of a mathematical implementation of the byte substitution function of AES using Galois Field operations is presented. A storage register 150 provides an 8-bit element of the AES state to a mapping module 152. The mapping module 152 decomposes the 8-bit element from GF(256) into two 4-bit values in GF(16). The two 4-bit values are output to a first squaring module 154 and a second squaring module 156, respectively.
The first and second squaring modules 154 and 156 square their inputs in GF(16). The output of the second squaring module 156 is multiplied with the hexadecimal value E by a first multiplication module 158. A first summation module 160 receives an output of the first multiplication module 158 and an output of the first squaring module 154.
The first and second values from the mapping module 152 are multiplied by a second multiplication module 162. Outputs of the second multiplication module 162 and the first summation module 160 are added by a second summation module 164, the result of which is output to an inversion module 166. An output of the inversion module 166 is output to third and fourth multiplication modules 168 and 170.
The first and second values from the mapping module 152 are summed by a third summation module 172, the result of which is output to the third multiplication module 168. The fourth multiplication module 170 receives the second value from the mapping module 152. The outputs of the multiplication modules 168 and 170 are received by an inverse mapping module 174, which composes the two four-bit values in GF(16) into an 8-bit output value in GF(256).
An affine transform 176 is applied to the output of the inverse mapping module 174. The output of the affine transform 176 is stored in another storage register 178. Because there are 16 elements in the AES state, there may be 16 copies of the S-box shown in FIG. 1B to process the 16 elements concurrently. Alternatively, one S-box can be used to process each of the 16 elements sequentially.
Further discussion of byte substitution can be found in Alireza Hodjat & Ingrid Verbauwhede, “Area-Throughput Trade-Offs for Fully Pipelined 30-to-70 GBits/s AES Processors,” IEEE Transactions on Computers, Vol. 55, No. 4, April 2006, the disclosure of which is incorporated herein by reference in its entirety.